# 有序列表
# import sortedcontainers
#
#
# class RangeModule:
#
#     def __init__(self):
#         self.st = sortedcontainers.SortedList()
#
#     def addRange(self, left: int, right: int) -> None:
#         add = [left, right]
#         index = self.st.bisect_right(add)
#         if index > 0:
#             last_index = index - 1
#             if self.st[last_index][1] >= add[0]:
#                 node = self.st.pop(last_index)
#                 add = [node[0], max(node[1], add[1])]
#                 index -= 1
#         while index < len(self.st) and add[1] >= self.st[index][0]:
#             node = self.st.pop(index)
#             add = [add[0], max(node[1], add[1])]
#         self.st.add(add)
#
#     def queryRange(self, left: int, right: int) -> bool:
#         index = self.st.bisect_right([left, right])
#         if index > 0:
#             last_index = index - 1
#             if self.st[last_index][0] <= left and self.st[last_index][1] >= right:
#                 return True
#         if index < len(self.st):
#             if self.st[index][0] <= left and self.st[index][1] >= right:
#                 return True
#         return False
#
#     def removeRange(self, left: int, right: int) -> None:
#         index = self.st.bisect_right([left, right])
#         rm = [left, right]
#         if index > 0:
#             last_index = index - 1
#             if self.st[last_index][1] > rm[0]:
#                 node = self.st.pop(last_index)
#                 if node[0] < rm[0]:
#                     self.st.add([node[0], rm[0]])
#                 else:
#                     index -= 1
#                 if node[1] == rm[1]:
#                     return
#                 if node[1] > rm[1]:
#                     self.st.add([rm[1], node[1]])
#                     return
#                 else:
#                     rm = [node[1], rm[1]]
#         while index < len(self.st) and rm[1] > self.st[index][0]:
#             node = self.st.pop(index)
#             if rm[1] > node[1]:
#                 rm = [node[1], rm[1]]
#             else:
#                 if rm[1] == node[1]:
#                     return
#                 else:
#                     self.st.add([rm[1], node[1]])
#                     return

# 动态展开树
class Treenode():
    def __init__(self):
        self.left = self.right = None
        self.val = False
        self.lazy = False

class RangeModule:

    def __init__(self):
        self.tree = Treenode()
        self.maxRange = 10 ** 9

    def addRange(self, left: int, right: int) -> None:
        self.update(self.tree, 1, self.maxRange, left, right - 1, True)

    def queryRange(self, left: int, right: int) -> bool:
        return self.query(self.tree, 1, self.maxRange, left, right - 1)

    def removeRange(self, left: int, right: int) -> None:
        self.update(self.tree, 1, self.maxRange, left, right - 1, False)

    def update(self, node, ls, rs, l, r, v):
        if l <= ls and r >= rs:
            node.val = v
            node.lazy = True
        else:
            self.down(node)
            mid = (ls + rs) // 2
            if l <= mid:
                self.update(node.left, ls, mid, l, r, v)
            if r >= mid + 1:
                self.update(node.right, mid + 1, rs, l, r, v)
            self.up(node)


    def query(self, node, ls, rs, l, r):
        if l <= ls and r >= rs:
            return node.val
        if l >= ls and r <= rs and node.val:
            return True
        self.down(node)
        mid = (ls + rs) // 2
        ans = True
        if l <= mid:
            ans &= self.query(node.left, ls, mid, l, r)
        if ans & (r >= mid + 1):
            ans &= self.query(node.right, mid + 1, rs, l, r)
        return ans


    def down(self, node):
        if not node.left:
            node.left = Treenode()
        if not node.right:
            node.right = Treenode()
        if not node.lazy:
            return
        node.left.val = node.right.val = node.val
        node.left.lazy = node.right.lazy = True
        node.lazy = False

    def up(self, node):
        node.val = node.left.val and node.right.val